//69 求开方
/*
给定一个非负整数，求它的开方，向下取整

输入输出样例
	输入一个整数，输出一个整数
	Input: 8
	Output: 2

分析：在1和该数之间逐个遍历，取二分查找
*/


int mySqrt(int a)
{
	if (a == 0)
		return a;
	int l = 1, r = a, mid, sqrt;
	while (l <= r)
	{
		mid = l + (r - l) / 2;
		sqrt = a / mid;
		if (sqrt == mid) //
		{
			return mid;
		}
		else if (mid > sqrt)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	return r;
}


//方法二：牛顿迭代法
int mySqrt(int a)
{
	long x = a;
	while (x * x > a)
	{
		x = (x + a / x) / 2;
	}
	return x;
}